////////////////////////////////////////////////////////////////////////////////
// This file is part of the Mist compiler.                                    //
//                                                                            //
// Copyright (C) 2009, 2010 The Mist project                                  //
//                                                                            //
// For a list of contributors, see the COMMITTERS file.                       //
//                                                                            //
// The Mist compiler is free software: you can redistribute it and/or modify  //
// it under the terms of the GNU General Public License as published by       //
// the Free Software Foundation, either version 3 of the License, or          //
// (at your option) any later version.                                        //
//                                                                            //
// The Mist compiler is distributed in the hope that it will be useful,       //
// but WITHOUT ANY WARRANTY; without even the implied warranty of             //
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the              //
// GNU General Public License for more details.                               //
//                                                                            //
// You should have received a copy of the GNU General Public License          //
// in the COPYING file. If not, see <http://www.gnu.org/licenses/>.           //
////////////////////////////////////////////////////////////////////////////////

///
/// \file
/// Contains the implementation of the Reference::Resolved methods from tree.hpp.
///

#include "tree.hpp"

////////////////////////////////////////////////////////////////////////////////
// Includes                                                                   //
////////////////////////////////////////////////////////////////////////////////

#include <stack>
using std::stack;

#include "copyast.hpp"
#include "symbol.hpp"

// 			#include <iostream>
// 			using std::cerr;

////////////////////////////////////////////////////////////////////////////////
// Forward Declarations                                                       //
////////////////////////////////////////////////////////////////////////////////

wptr<Symbol> resolve_reference(wptr<Reference> reference);

void eliminate_candidates(wptr<Reference> ref, set<wptr<Symbol> >& candidates, vector<wptr<Type> >& templateInstantiation);

////////////////////////////////////////////////////////////////////////////////
// Function Implementations                                                   //
////////////////////////////////////////////////////////////////////////////////

void Reference::Resolved::set_reference(wptr<Reference> reference) {
	_reference = reference;
}

void Reference::Resolved::compute_value() {
	wptr<Symbol> symbol = resolve_reference(_reference);
	if (symbol)
		set_value(symbol);
	else
		set_error();
}

////////////////////////////////////////////////////////////////////////////////
// 
wptr<Symbol> resolve_reference(wptr<Reference> reference) {
	assert(reference);
	
	stack<wptr<Symbol> > seen;
	
	// Make a list of the parts of the reference, left to right.
	//
	vector<wptr<Reference> > refA;
	for (wptr<Reference> r = reference; r; r = r->scopePart)
		refA.insert(refA.begin(), r);
	
	// breadCrumbs stores the trail through the symbol hierarchy from the current
	// scope up to the scope in which refA[0] is visible. Or, if appropriate, to
	// the root scope.
	//
	stack<wptr<Symbol> > breadCrumbs;
	
	if (!refA[0]->namePart) {
		// If we have an absolute reference, we lay a breadcrumb trail to the root.
		//
		wptr<Symbol> s = reference->scope();
		for (; s->parent; s = s->parent)
			breadCrumbs.push(s);
		breadCrumbs.push(s);
		
		// We know to start searching from the second part of the reference.
		// (The first part represented the 'absoluteness' of the reference.)
		//
		refA.erase(refA.begin());
	} else {
		// For a relative reference, we lay a breadcrumb trail up to the first
		// symbol with the right child corresponding to refA[0]'s name-part.
		//
		bool found = false;
		for (wptr<Symbol> s = reference->scope(); s && !found; s = s->parent) {
			breadCrumbs.push(s);
			if (s->childrenByName.count(*refA[0]->namePart))
				found = true;
		}
		
		// If we've searched from scope to root, but the first part of the path
		// was not found, return failure, the null pointer.
		//
		if (!found)
			return wptr<Symbol>();
	}
	
	// We are now left with a relative path in refA. We follow it, able to walk
	// free over the breadcrumb trail, but also able to cross transparent scopes
	// if necessary.
	//
	wptr<Symbol> current = breadCrumbs.top();
	breadCrumbs.pop();
	for (uint refi = 0; refi < refA.size();) {
		wptr<Reference> ref = refA[refi];
		bool lastRefPart = (refi + 1 == refA.size());
		
		typedef multimap<TypeSpec, wptr<Symbol>, TypeSpec::Before> MM;
		typedef map<string, MM> M;
		
		// Get the candidates with the right name.
		//
		set<wptr<Symbol> > candidates;
		M::iterator it = current->childrenByName.find(*ref->namePart);
		if (it != current->childrenByName.end()) {
			foreach (MM::value_type childPair, it->second) {
				if (!childPair.second->declaration || !childPair.second->declaration->isTemplateInstantiation)
					candidates.insert(childPair.second);
			}
		}
		
		// If there was no child with the right name, we see if the next
		// breadcrumb introduces no scope, so we can walk it for free.
		//
		if (candidates.size() == 0 && !breadCrumbs.empty() && !breadCrumbs.top()->newScope) {
			current = breadCrumbs.top();
			breadCrumbs.pop();
			continue;
		}
		
		// Ok, let's see which candidates are compatible with the reference.
		//
		vector<wptr<Type> > templateInstantiations;
		eliminate_candidates(ref, candidates, templateInstantiations);
		
		if (candidates.size() == 1) {
			bool allTemplateInstantiationsKnown = true;
			foreach (wptr<Type> ti, templateInstantiations)
				allTemplateInstantiationsKnown &= (bool)ti;
			
			if (allTemplateInstantiationsKnown) {
				if (!breadCrumbs.empty() && *candidates.begin() == breadCrumbs.top()) {
					breadCrumbs.pop();
					goto candidate_found;
				}
				
				if (current->transparent || lastRefPart)
					goto candidate_found;
			}
			// TODO: Error, reference not found
		}
		
		if (candidates.size() > 1) {
			// TODO: Error, ambiguous reference
		}
		 
		if (candidates.size() == 0) {
			// TODO: Error, reference not found
		}
		
		return wptr<Symbol>();
		
		candidate_found: {
			current = *candidates.begin();
			
			// Add new template instantation of the function.
			//
			if (current->type && typeid(*current->type) == typeid(FunctionType) && templateInstantiations.size()) {
				if (!current->templateInstantiations.count(templateInstantiations)) {
					map<wptr<Symbol>, sptr<Node> > mp;
					for (uint i = 0; i < templateInstantiations.size(); ++i)
						mp[current->typeSpec->templateTypeSpec[i]->symbol] = copy(templateInstantiations[i]);
					sptr<FunctionDeclaration> newDeclaration = copy(current->declaration, mp);
					newDeclaration->parent = current->declaration->parent;
					newDeclaration->templateTypeNames = vector<sptr<Identifier> >();
					newDeclaration->isTemplateInstantiation = true;
					current->templateInstantiations[templateInstantiations] = newDeclaration;
				}
				
				current = current->templateInstantiations[templateInstantiations]->paramScope();
			}
			++refi;
		}
	}
	
	return current;
}

void eliminate_candidates(wptr<Reference> ref, set<wptr<Symbol> >& candidates, vector<wptr<Type> >& templateInstantiation) {
	// Declare and initialize the working formal type specification
	// of the reference.
	//
	optional<vector<sptr<Type> > > formalTypeSpec = ref->formalTypeSpec;
	if (!formalTypeSpec && ref->parent && typeid(*ref->parent) == typeid(FunctionCall)
		&& sptr<Reference>(ref) == ref->parent.cast<FunctionCall>()->base) {
		formalTypeSpec = vector<sptr<Type> >();
		foreach (wptr<Expression> p, ref->parent.cast<FunctionCall>()->parameters)
			formalTypeSpec->push_back(p->type());
	}
	// Eliminate any candidate with the wrong number of formal
	// parameters.
	//
	if (formalTypeSpec) {
		foreach (wptr<Symbol> candidate, candidates) {
			if (candidate->typeSpec && candidate->typeSpec->formalTypeSpec.size() != formalTypeSpec->size())
				candidates.erase(candidate);
		}
	}
	// Did the reference explicitly specify template types?
	//
	if (ref->templateTypeSpec) {
		// Fill in template instantiation.
		//
		templateInstantiation = weak_vector(*ref->templateTypeSpec);
		
		// Eliminate any candidates with the wrong number of template
		// parameters.
		//
		foreach (wptr<Symbol> candidate, candidates)
			if (candidate->typeSpec && candidate->typeSpec->templateTypeSpec.size() != ref->templateTypeSpec->size())
				candidates.erase(candidate);
		
		// Did the reference specify the formal parameter types? Either
		// by !() notation or function-call parameters?
		//
		if (formalTypeSpec) {
			// Eliminate any candidate that does not have an exact
			// formal parameter type match with the reference.
			//
			foreach (wptr<Symbol> candidate, candidates) {
				map<wptr<Symbol>, wptr<Type> > mp;
				for (uint i = 0; i < templateInstantiation.size(); ++i)
					mp[candidate->typeSpec->templateTypeSpec.at(i)->symbol] = templateInstantiation.at(i);
				
				for (uint i = 0; i < formalTypeSpec->size(); ++i) {
					if (!candidate->typeSpec || !same_type(candidate->typeSpec->formalTypeSpec.at(i), formalTypeSpec->at(i), mp)) {
						candidates.erase(candidate);
						break;
					}
				}
			}
		}
	} else {
		// The reference did not explicitly specify template types.
		
		if (formalTypeSpec) {
			foreach (wptr<Symbol> candidate, candidates) {
				map<wptr<Symbol>, wptr<Type> > mp;
				if (candidate->typeSpec) {
					foreach (wptr<Identifier> id, candidate->typeSpec->templateTypeSpec) {
						mp[id->symbol]; // Set null.
					}
				}
				
				bool same = true;
				for (uint i = 0; same && i < formalTypeSpec->size(); ++i) {
					if (!candidate->typeSpec || !same_type(formalTypeSpec->at(i), candidate->typeSpec->formalTypeSpec.at(i), mp)) {
						same = false;
						break;
					}
				}
				
				if (same) {
					templateInstantiation.clear();
					foreach (wptr<Identifier> id, candidate->typeSpec->templateTypeSpec)
						templateInstantiation.push_back(mp[id->symbol]);
				} else {
					candidates.erase(candidate);
				}
			}
		} else if (!candidates.empty()) {
			// Fill the templateInstantiations vector with as many nulls as any
			// arbitrary candidate. We're assuming that it won't go through unless
			// this candidate is the only one.
			//
			map<wptr<Symbol>, wptr<Type> > mp;
			if ((*candidates.begin())->typeSpec) {
				foreach (wptr<Identifier> id, (*candidates.begin())->typeSpec->templateTypeSpec) {
					templateInstantiation.push_back(wptr<Type>());
				}
			}
		}
	}
}
